{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimize Max Distance to Gas Station"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minmaxGasDist"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小化去加油站的最大距离"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>整数数组 <code>stations</code> 表示 <strong>水平数轴</strong> 上各个加油站的位置。给你一个整数 <code>k</code> 。</p>\n",
    "\n",
    "<p>请你在数轴上增设 <code>k</code> 个加油站，新增加油站可以位于 <strong>水平数轴</strong> 上的任意位置，而不必放在整数位置上。</p>\n",
    "\n",
    "<p>设 <code>penalty()</code> 是：增设 <code>k</code> 个新加油站后，<strong>相邻</strong> 两个加油站间的最大距离。</p>\n",
    "请你返回 <code>penalty()</code><strong> </strong>可能的最小值。与实际答案误差在 <code>10<sup>-6</sup></code> 范围内的答案将被视作正确答案。\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>stations = [1,2,3,4,5,6,7,8,9,10], k = 9\n",
    "<strong>输出：</strong>0.50000\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>stations = [23,24,36,39,46,56,57,65,84,98], k = 1\n",
    "<strong>输出：</strong>14.00000\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>10 <= stations.length <= 2000</code></li>\n",
    "\t<li><code>0 <= stations[i] <= 10<sup>8</sup></code></li>\n",
    "\t<li><code>stations</code> 按 <strong>严格递增</strong> 顺序排列</li>\n",
    "\t<li><code>1 <= k <= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimize-max-distance-to-gas-station](https://leetcode.cn/problems/minimize-max-distance-to-gas-station/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimize-max-distance-to-gas-station](https://leetcode.cn/problems/minimize-max-distance-to-gas-station/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5,6,7,8,9,10]\\n9', '[23,24,36,39,46,56,57,65,84,98]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# ### my：贪心+二分（refer 1231/410）\n",
    "# class Solution:\n",
    "#     def minmaxGasDist(self, stations: List[int], k: int) -> float:\n",
    "#         right=0\n",
    "#         n=len(stations)\n",
    "#         for i in range(1,n):\n",
    "#             right=max(right,stations[i]-stations[i-1])\n",
    "#         left=0\n",
    "#         def check(x):\n",
    "#             cnt=0\n",
    "#             for i in range(1,n):\n",
    "#                 # cnt+=(stations[i]-stations[i-1])//(x+0.01)\n",
    "#                 cnt+=int((stations[i]-stations[i-1])/x)\n",
    "#             return cnt<=k\n",
    "\n",
    "#         # while left<right:\n",
    "#         # while left<right-1e-6:\n",
    "#         while right-left>1e-6:### 这个条件使得（A）处left可以==mid\n",
    "#             # mid=(left+right)//2\n",
    "#             mid=(left+right)/2.0\n",
    "#             if check(mid):\n",
    "#                 right=mid \n",
    "#             else:\n",
    "#                 left=mid+1e-6 #+1  ###（A）\n",
    "#         return left\n",
    "            \n",
    "### 官4：贪心+二分查找（原码）\n",
    "class Solution(object):\n",
    "    def minmaxGasDist(self, stations, K):\n",
    "        def possible(D):\n",
    "            return sum(int((stations[i+1] - stations[i]) / D)\n",
    "                       for i in range(len(stations) - 1)) <= K\n",
    "\n",
    "        lo, hi = 0, 10**8\n",
    "        while hi - lo > 1e-6:\n",
    "            mi = (lo + hi) / 2.0\n",
    "            if possible(mi):\n",
    "                hi = mi\n",
    "            else:\n",
    "                lo = mi\n",
    "        return lo\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def station_needed(self, d, in_list):\n",
    "        res = 0\n",
    "        for i in in_list:\n",
    "            res += int(i/d)\n",
    "        return res\n",
    "    def minmaxGasDist(self, stations: List[int], k: int) -> float:\n",
    "        res = []\n",
    "        for i in range(len(stations)):\n",
    "            if i == 0:\n",
    "                pass\n",
    "            else:\n",
    "                res.append(stations[i] - stations[i-1])\n",
    "        left = 0\n",
    "        right = 10 ** 8\n",
    "        while right - left > 1/(10 ** 6):\n",
    "            mid = (left + right) / 2\n",
    "            if self.station_needed(mid, res) <= k:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid\n",
    "        return left\n",
    "        \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    1 , 4, 6\n",
    "    range [0, end - start]\n",
    "    '''\n",
    "    def minmaxGasDist(self, stations: List[int], k: int) -> float:\n",
    "\n",
    "        left = 0\n",
    "        right = stations[-1] - stations[0]\n",
    "\n",
    "        while right - left >= 10 ** -6:\n",
    "            mid = (left + right) / 2\n",
    "\n",
    "            if self.enough(mid, stations, k):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid\n",
    "\n",
    "        return left\n",
    "\n",
    "\n",
    "    def enough(self, mid, stations, k):\n",
    "        for i in range(1, len(stations)):\n",
    "            gap = stations[i] - stations[i - 1]\n",
    "            k -= gap//mid\n",
    "\n",
    "        return k >= 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minmaxGasDist(self, stations: List[int], k: int) -> float:\n",
    "        left, right = 0, stations[-1]\n",
    "\n",
    "        def possible(mid):\n",
    "            return sum(int((stations[i+1] - stations[i]) / mid) for i in range(len(stations) - 1)) <= k\n",
    "\n",
    "        while right - left > 1e-6:\n",
    "            mid = (right + left) / 2.0\n",
    "            if possible(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid\n",
    "        \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "二分搜索最大的D，让每个加油站之间的距离都小于等于D且总共新加的加油站个数小于等于K\n",
    "'''\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    # 验证需要保证所有加油站距离都小于等于D的情况下，K个新加的加油站是否够用\n",
    "    def isValid(self, D, dis, K):\n",
    "        cnt = 0\n",
    "        for d in dis:\n",
    "            val = (d / D)\n",
    "            floor_val = math.floor(val)\n",
    "            if floor_val == val:\n",
    "                cnt += int(floor_val) - 1\n",
    "            else:\n",
    "                cnt += int(floor_val)\n",
    "\n",
    "            if cnt > K:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def minmaxGasDist(self, stations: List[int], K: int) -> float:\n",
    "        dis = []\n",
    "        max_dis = -1\n",
    "        for i in range(1, len(stations)):\n",
    "            d = stations[i] - stations[i-1]\n",
    "            dis.append(stations[i] - stations[i-1])\n",
    "            max_dis = max(max_dis, d)\n",
    "\n",
    "        l, r = 0, max_dis\n",
    "        ans = -1.0\n",
    "        while r - l >= 10 ** (-6):\n",
    "            mid = l + (r - l) / 2\n",
    "            if self.isValid(mid, dis, K):\n",
    "                ans = mid\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    1 , 4, 6\n",
    "    range [0, end - start]\n",
    "    '''\n",
    "    def minmaxGasDist(self, stations: List[int], k: int) -> float:\n",
    "\n",
    "        left = 0\n",
    "        right = stations[-1] - stations[0]\n",
    "\n",
    "        while right - left >= 10 ** -6:\n",
    "            mid = (left + right) / 2\n",
    "\n",
    "            if self.enough(mid, stations, k):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid\n",
    "\n",
    "        return left\n",
    "\n",
    "\n",
    "    def enough(self, mid, stations, k):\n",
    "        for i in range(1, len(stations)):\n",
    "            gap = stations[i] - stations[i - 1]\n",
    "            k -= gap//mid\n",
    "\n",
    "        return k >= 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minmaxGasDist(self, stations: List[int], k: int) -> float:\n",
    "        l,r = 0,10**8\n",
    "        def check(mid):\n",
    "            cnt = 0\n",
    "            for x,y in pairwise(stations):\n",
    "                d = y - x\n",
    "                cnt += ceil(d / mid - 1)\n",
    "            return cnt <= k        \n",
    "        \n",
    "        while r - l > 1e-6:\n",
    "            mid = (l + r) / 2\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minmaxGasDist(self, stations: List[int], k: int) -> float:\n",
    "        \n",
    "        def countk(dist):\n",
    "            num = 0\n",
    "            for i in range(1, len(stations)):\n",
    "                num += int((stations[i] - stations[i - 1]) / dist)\n",
    "            return num\n",
    "\n",
    "\n",
    "        left, right = 0, stations[-1] - stations[0]\n",
    "        while left + 1e-6 < right:\n",
    "            mid = (left + right) / 2\n",
    "            # 算出来的个数比需要的k多，说明要求的间距小了，需要增加\n",
    "            if countk(mid) > k:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        # 找出最小的penalty的值\n",
    "        if countk(left) <= k:\n",
    "            return left\n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minmaxGasDist(self, stations: List[int], k: int) -> float:\n",
    "        def check(x):\n",
    "            res = 0\n",
    "            for a,b in pairwise(A):\n",
    "                res += (b-a-1)//x\n",
    "            return res<=k\n",
    "\n",
    "        A = [a*10**6 for a in stations]\n",
    "        return (bisect_left(range(1,A[-1]-A[0]),True,key=check)+1)/(10**6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    1 , 4, 6\n",
    "    range [0, end - start]\n",
    "    '''\n",
    "    def minmaxGasDist(self, stations: List[int], k: int) -> float:\n",
    "\n",
    "        left = 0\n",
    "        right = stations[-1] - stations[0]\n",
    "\n",
    "        while right - left >= 10 ** -6:\n",
    "            mid = (left + right) / 2\n",
    "\n",
    "            if self.enough(mid, stations, k):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid\n",
    "\n",
    "        return left\n",
    "\n",
    "\n",
    "    def enough(self, mid, stations, k):\n",
    "        for i in range(1, len(stations)):\n",
    "            gap = stations[i] - stations[i - 1]\n",
    "            k -= int(gap/mid) \n",
    "\n",
    "        return k >= 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minmaxGasDist(self, stations: List[int], k: int) -> float:\n",
    "        left = 0.0\n",
    "        right = float(stations[-1]-stations[0])\n",
    "        for i in range(len(stations)-1):\n",
    "            stations[i] = stations[i+1]-stations[i]\n",
    "        stations[-1] = 0\n",
    "        mid = (left+right)/2\n",
    "\n",
    "        while right-left>=1e-6:\n",
    "            print(left, mid, right)\n",
    "            p = k\n",
    "            for i in range(len(stations)-1):\n",
    "               if stations[i]>mid:\n",
    "                #    print(stations[i], mid)\n",
    "                   p -= math.ceil(stations[i]/mid)-1\n",
    "            # print(p)\n",
    "            if p < 0:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid-1e-6\n",
    "            mid = (left+right)/2\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minmaxGasDist(self, stations: List[int], k: int) -> float:\n",
    "        l,r=0,100000000.0\n",
    "\n",
    "        check=lambda x: sum(ceil((stations[i]-stations[i-1])/x) - 1 for i in range(1,len(stations)))\n",
    "        while l<r:\n",
    "            print(l,r)\n",
    "            if abs(l-r)<1e-6:\n",
    "                break\n",
    "            mid=(l+r)/2\n",
    "            if check(mid)==k:\n",
    "                r=mid\n",
    "            elif check(mid)>k:\n",
    "                l=mid\n",
    "            elif check(mid)<k:\n",
    "                r=mid\n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minmaxGasDist(self, stations, K):\n",
    "        def possible(D):\n",
    "            return sum(int((stations[i+1] - stations[i]) / D)\n",
    "                       for i in range(len(stations) - 1)) <= K\n",
    "\n",
    "        lo, hi = 0, 10**8\n",
    "        while hi - lo > 1e-6:\n",
    "            mi = (lo + hi) / 2.0\n",
    "            if possible(mi):\n",
    "                hi = mi\n",
    "            else:\n",
    "                lo = mi\n",
    "        return lo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minmaxGasDist(self, stations: List[int], k: int) -> float:\n",
    "        l,r = 0,10**8\n",
    "        def check(mid):\n",
    "            cnt = 0\n",
    "            for x,y in pairwise(stations):\n",
    "                d = y - x\n",
    "                cnt += ceil(d / mid - 1)\n",
    "            return cnt <= k        \n",
    "        \n",
    "        while r - l > 1e-6:\n",
    "            mid = (l + r) / 2\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minmaxGasDist(self, stations: List[int], k: int) -> float:\n",
    "        l,r=0.0001,100000000.0\n",
    "\n",
    "        check=lambda x: sum(ceil((stations[i]-stations[i-1])/x) - 1 for i in range(1,len(stations)))\n",
    "        while l<r:\n",
    "            print(l,r)\n",
    "            if abs(l-r)<1e-6:\n",
    "                break\n",
    "            mid=(l+r)/2\n",
    "            if check(mid)==k:\n",
    "                r=mid\n",
    "            elif check(mid)>k:\n",
    "                l=mid\n",
    "            elif check(mid)<k:\n",
    "                r=mid\n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minmaxGasDist(self, stations: List[int], k: int) -> float:\n",
    "        l,r=0,100000000\n",
    "\n",
    "        check=lambda x: sum(ceil((stations[i]-stations[i-1])/x) - 1 for i in range(1,len(stations)))\n",
    "        while l<r:\n",
    "            print(l,r)\n",
    "            if abs(l-r)<1e-6:\n",
    "                break\n",
    "            mid=(l+r)/2\n",
    "            if check(mid)==k:\n",
    "                r=mid\n",
    "            elif check(mid)>k:\n",
    "                l=mid\n",
    "            elif check(mid)<k:\n",
    "                r=mid\n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minmaxGasDist(self, stations: List[int], k: int) -> float:\n",
    "        eps = 1e-8\n",
    "\n",
    "        n = len(stations)\n",
    "        dist = []\n",
    "        for i in range(n - 1):\n",
    "            dist.append(stations[i+1] - stations[i])\n",
    "\n",
    "        def check(mid: int) -> bool:\n",
    "            need = 0\n",
    "            for d in dist:\n",
    "                need += int(d / mid)\n",
    "            return need <= k\n",
    "\n",
    "        l = 0\n",
    "        r = 10 ** 8\n",
    "        while l < r - eps:\n",
    "            mid = (l + r) / 2\n",
    "            if check(mid) == True:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + eps\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minmaxGasDist(self, stations: List[int], k: int) -> float:\n",
    "        \n",
    "        def countk(dist):\n",
    "            num = 0\n",
    "            for i in range(1, len(stations)):\n",
    "                num += int((stations[i] - stations[i - 1]) / dist)\n",
    "            return num\n",
    "\n",
    "\n",
    "        left, right = 0, stations[-1] - stations[0]\n",
    "        while left + 1e-6 < right:\n",
    "            mid = (left + right) / 2\n",
    "            # 算出来的个数比需要的k多，说明要求的间距小了，需要增加\n",
    "            if countk(mid) > k:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        # 找出最小的penalty的值\n",
    "        if countk(left) <= k:\n",
    "            return left\n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minmaxGasDist(self, stations: List[int], k: int) -> float:\n",
    "        n = len(stations)\n",
    "        dist = []\n",
    "        for i in range(1, n):\n",
    "            dist.append(stations[i]-stations[i-1])\n",
    "        l, r = 0, max(dist)\n",
    "        while r - l > 1e-6:\n",
    "            mid = (r + l)/2\n",
    "            need = k\n",
    "            for d in dist:\n",
    "                need -= int(d/mid)\n",
    "                if need < 0:\n",
    "                    l = mid\n",
    "                    break\n",
    "            if need >= 0:\n",
    "                r = mid\n",
    "        return l\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
